package leetcode.code673;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution3 extends Solution673 {

	@Override
	public int findNumberOfLIS(int[] nums) {
		Stack<Integer> s1 = new Stack<>();
		Stack<Integer> s2 = new Stack<>();
		Map<Integer, Map<Integer, Integer>> numsoflen = new HashMap<>();
		s1.add(nums[0]);
		Map<Integer, Integer> map = new HashMap<>();
		map.put(nums[0], 1);
		numsoflen.put(1, map);
		for (int i = 1; i < nums.length; i++) {
			if (s1.peek() < nums[i]) {
				s1.add(nums[i]);
				this.updateTotal(s1.size(), nums[i], numsoflen);
			} else if (s1.peek() > nums[i]) {
				while (!s1.isEmpty() && s1.peek() >= nums[i]) {
					s2.add(s1.pop());
				}
				s2.pop();
				s1.add(nums[i]);
				this.updateTotal(s1.size(), nums[i], numsoflen);
				while (!s2.isEmpty()) {
					s1.add(s2.pop());
				}
			} else if (s1.peek() == nums[i]) {
				this.updateTotal(s1.size(), nums[i], numsoflen);
			}
		}
		int total = 0;
		map = numsoflen.get(s1.size());
		for (Integer key : map.keySet()) {
			total += map.get(key);
		}
		return total;
	}

	/**
	 * 更新level位，数字为cur的numsoflen信息
	 * @param level
	 * @param cur
	 * @param numsoflen
	 */
	private void updateTotal(int level, int cur, Map<Integer, Map<Integer, Integer>> numsoflen) {
		int total = 0;
		Map<Integer, Integer> map = numsoflen.getOrDefault(level - 1, null);
		if (map != null) {
			for (int num : map.keySet()) {
				if (num < cur) {
					total += map.get(num);
				}
			}
		}
		map = numsoflen.getOrDefault(level, new HashMap<>());
		total = total == 0 ? 1 : total;
		total += map.getOrDefault(cur, 0);
		map.put(cur, total);
		numsoflen.put(level, map);
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
